"""
我们创建了一个 Node 类，在其中定义了一个 __init__ 函数，
以使用作为参数传递的数据和带有 None 的引用来初始化节点，
因为如果我们只有一个节点，那么它的引用中就没有任何内容

"""


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


"""

"""


class LinkedList:
    def __init__(self):
        self.head = None

    """
该方法将节点插入到链表的开头。在这种方法中，
我们使用给定的数据创建一个new_node并检查 head 是否为空，
然后我们将 new_node 设为 head 并返回，
否则我们在下一个new_node插入 head 并使 head 等于 new_node。
    """

    def insertAtBegin(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        else:
            new_node.next = self.head
            self.head = new_node

    """
此方法在链表中的给定索引处插入节点。在这种方法中，我们创建一个 new_node 给定数据 ，
一个等于 head 的 current_node，并且计数器 'position' 初始化为 0。现在，
如果索引等于零，则意味着节点将在开始时插入，因此我们调用 insertAtBegin（） 方法，
否则我们运行 while 循环，直到current_node不等于 None 或 （position+1） 不等于我们必须在一个位置
返回插入到给定位置以链接节点，并在每次迭代中， 我们将位置增加 1，并将 current_node 设为下一个位置。
当循环中断并且 current_node 不等于 None 时，我们将 new_node at after 插入到current_node。
如果 current_node 等于 None，则表示列表中不存在索引，我们打印 “Index not present”。
   """

    def insertAtIndex(self, data, index):
        if (index == 0):
            self.insertAtBegin(data)

        position = 0
        current_node = self.head
        while (current_node != None and position + 1 != index):
            position = position + 1
            current_node = current_node.next

        if current_node != None:
            new_node = Node(data)
            new_node.next = current_node.next
            current_node.next = new_node
        else:
            print("Index not present")

    """
    此方法将节点插入到链表的末尾。在这种方法中，我们使用给定的数据创建一个new_node并检查 head 是否为空，
    然后我们将new_node设为 head 并返回，否则我们制作一个等于 head 遍历到链表最后一个节点的current_node，
    当我们current_node后得到 None 时，
    while 循环中断并插入new_node在 current_node 的下一个节点中，这是链表的最后一个节点。
    """

    def insertAtEnd(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return

        current_node = self.head
        while (current_node.next):
            current_node = current_node.next

        current_node.next = new_node

    """
此代码在链表类中定义了一个名为 updateNode 的方法。它用于更新链表中给定位置的节点的值
    """

    def updateNode(self, val, index):
        current_node = self.head
        position = 0
        if position == index:
            current_node.data = val
        else:
            while (current_node != None and position != index):
                position = position + 1
                current_node = current_node.next

            if current_node != None:
                current_node.data = val
            else:
                print("Index not present")

    """
    此方法只需将链表的第二个节点设为 head 即可删除链表的第一个节点。
    """

    def remove_first_node(self):
        if (self.head == None):
            return

        self.head = self.head.next

    """
在此方法中，我们将删除最后一个节点。
首先，我们使用 while 循环遍历到倒数第二个节点，
然后将该节点的下一个节点设为 None，最后一个节点将被删除。
    """

    def remove_last_node(self):

        if self.head is None:
            return

        current_node = self.head
        while (current_node != None and current_node.next.next != None):
            current_node = current_node.next

        current_node.next = None

    """
    在此方法中，我们将删除给定索引处的节点，此方法类似于 insert_at_inded（） 方法。
    在这个方法中，如果 head 是 None，我们只需返回，否则我们用 self.head 初始化一个 current_node，
    用 0 初始化一个 position。如果位置等于我们调用 remove_first_node（） 方法的索引，
    否则我们使用 while 循环遍历到我们想要删除的节点之前的节点。循环一直持续，
    直到 current_node 为 None 或 position 达到索引 – 1。在循环之后，我们检查 current_node
    或 current_node.next 是否为 None。如果 current_node 为 None，
    则表示索引超出范围。如果没有，则我们绕过要删除的节点。
    """

    def remove_at_index(self, index):
        if self.head == None:
            return

        current_node = self.head
        position = 0
        if position == index:
            self.remove_first_node()
        else:
            while (current_node != None and position + 1 != index):
                position = position + 1
                current_node = current_node.next

            if current_node != None:
                current_node.next = current_node.next.next
            else:
                print("Index not present")

    """
    此方法从链表中删除具有给定数据的节点。在这个方法中，
    首先我们制作了一个等于 head 的 current_node，并运行一个 while 循环来遍历链表。
    当 while 循环变为 None 或当前节点旁边的数据等于参数中给定的数据时current_node while 循环将中断。
    现在，在退出循环后，如果 current_node 等于 None，则意味着该节点不存在于数据中，
    我们只返回，如果current_node旁边的数据等于给定的数据，
    那么我们通过将该removed_node的下一个current_node来删除该节点。这是使用 if else 条件实现的。
    """

    def remove_node(self, data):
        current_node = self.head

        if current_node.data == data:
            self.remove_first_node()
            return

        while (current_node != None and current_node.next.data != data):
            current_node = current_node.next

        if current_node == None:
            return
        else:
            current_node.next = current_node.next.next

    """
    此方法返回链表的大小。在这个方法中，我们用 0 初始化了一个计数器 'size'，然后如果 head 不等于 None，
    我们使用 while 循环遍历链表，并在每次迭代中将大小增加 1，
    并在 current_node 变为 None else 时返回大小，我们返回 0。
    """

    def sizeOfLL(self):
        size = 0
        if (self.head):
            current_node = self.head
            while (current_node):
                size = size + 1
                current_node = current_node.next
            return size
        else:
            return 0

    """
    该方法遍历链表并打印每个节点的数据。在这个方法中，我们制作了一个等于 head 的 current_node，
    并使用 while 循环遍历链表，
    直到current_node变为 None，并在每次迭代中打印 current_node 的数据，
    并在其旁边制作 current_node。
    """

    def printLL(self):
        current_node = self.head
        while (current_node):
            print(current_node.data)
            current_node = current_node.next


############################################
"""
在这个例子中，在定义了 Node 和 LinkedList 类之后，我们使用链表类创建了一个名为 “llist” 的链表，
然后在链表中插入四个字符数据为 'a'、'b'、'c'、'd' 和 'g' 的节点，然后我们使用 printLL（） 方法链表类打印链表，
之后我们使用 remove 方法删除了一些节点，然后再次打印链表，我们可以看到成功删除节点的输出。之后，我们还打印链表的大小。
"""

llist = LinkedList()

llist.insertAtEnd('a')
llist.insertAtEnd('b')
llist.insertAtBegin('c')
llist.insertAtEnd('d')
llist.insertAtIndex('g', 2)

print("Node Data")
llist.printLL()

print("\nRemove First Node")
llist.remove_first_node()
print("Remove Last Node")
llist.remove_last_node()
print("Remove Node at Index 1")
llist.remove_at_index(1)

print("\nLinked list after removing a node:")
llist.printLL()

print("\nUpdate node Value")
llist.updateNode('z', 0)
llist.printLL()

print("\nSize of linked list :", end=" ")
print(llist.sizeOfLL())
